public class MinCostClimbingStairs {
    // 最小花费爬楼梯
    // https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        // 状态表示:dp[i]表示跳到第i阶台阶所需要的最小的花费
        // 状态转移方程：因为第i阶台阶可以从第i-1和第i-2阶台阶，
        // 所以dp[i] = min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1])
        int[] dp = new int[cost.length+1];
        // 初始化，对于第0阶和第1阶台阶来说，因为可以直接从第0阶和第1阶开始，所以
        // dp[0] = dp[1] = 0
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }
}
